package demo.algorithm;


import org.HdrHistogram.*;
import org.junit.Test;

import java.net.DatagramSocket;
import java.net.SocketException;
import java.util.Collection;

/**
 * 分位数计算。
 * 很多人使用监控指标时存在一定困惑：
 *
 * <li>为什么要使用p95而不是平均值
 * <li>p95是不是过于灵敏导致误报
 * <li>客户端定义多少个Bin比较合适，Bin之间的步长为什么不设为定长
 *
 * @see <a href="https://zhuanlan.zhihu.com/p/26763580">统计学与监控</a>
 */
public class QuantileDemo {


    /**
     * 均值：很多时候大家喜欢使用均值来监控请求延时，主要在于其更好计算。
     * 对于数据集X=[x1, ..., xn]，均值的计算如下：mean(X):  return sum(X) / len(X)
     *
     * @return
     */
    public double meanValue(Collection<Number> collection) {
        double sum = 0.0;
        for (Number number : collection) {
            sum += number.doubleValue();
        }
        return sum / collection.size();
    }


    private static double total = 0.0;
    private static int count = 0;

    /**
     * 对一个在线服务，我们通常需要时刻刷新均值但又要限制内存使用量，一般采用下面的算法：
     * 只需要维护total和n两个值，然后不断更新即可计算出当前的均值。
     *
     * @return
     */
    public double meanValue(Number x) {
        total += x.doubleValue();
        count += 1;
        return total / count;
    }

    /**
     * Histogram是这样一种数据结构，首先它有一个取值范围[MinVal, MaxVal]，
     * 然后再取值范围内按照一定步长将取值区间换分为多个Bin/Bucket（桶），每个桶记录分布到该区间数值的个数。
     * <p>
     * 实际上Histogram对应于统计学中的Probability Density Function（概率密度函数）。
     * 当数据足够多，桶的分布足够合理，就可以计算出误差很小的φ-quantiles（经验显示可以控制在百分之1）。
     * <p>
     * 如何计算φ-quantiles？
     * φ的值理论上可以是任意0-1直接任意一个值，显然Quantile的值很有可能落在两个Bin之间。
     * Prometheus采用Linear interpolation（线性插值）来计算Quantile。线性插值首先假设数据的分布是线性的，
     * 如果x处于一组相邻的数据(x1, y1)和(x2, y2)之间求对应的y值，则首先算出相邻数据的slop（斜率），然后再使用point-slop（点斜）式计算出y值：
     * <p>
     * linear_interpolation_point(x1, y1, x2, y2, x):
     * slop = (y2-y1)/(x2-x1)
     * return slop(x-x1)+y1
     * <p>
     * 再去看promql/quantile.go的bucketQuantile()就豁然开朗了：
     * return bucketStart + (bucketEnd-bucketStart)*(rank/count)
     * <p>
     * Bucket Range：影响φ-quantiles计算精度的一个因素：桶距。
     * 考虑到延时类的实际分布情况，合理的桶距，应该是靠近MinVal侧桶距较小，而靠近MaxVal一侧桶距较大。
     * 具有这种特点的Histogram被称为Linear Histogram。
     * <p>
     * 下面是一种可能的实现：
     * <pre>
     * init_bucket_range(minVal, maxVal, bucket_count)
     *     log_max = log(maximum)
     *     bucket_index = 1
     *     current = minVal
     *     ranges[bucket_index] = current
     *     while (bucket_count > ++bucket_index)
     *     {
     *         log_current = log(current)
     *         log_ratio = (log_max - log_current) / (bucket_count - bucket_index);
     *         log_next = log_current + log_ratio
     *         next = (floor(exp(log_next) + 0.5))
     *         if (next > current)
     *             current = next
     *         else
     *             ++current
     *         ranges[bucket_index] = current
     *     }
     * <pre/>
     * 这个算法能比较好的保证桶距在左侧分布较密，右侧分布稀疏。
     *
     * 除此以外，HdrHistogram也提供了一种类似算法(n-significant-digitas)，
     */
    @Test
    public void testHistogram() {
        // 需指定预估的最大值
        Histogram histogram = new Histogram(5400000000000L, 4);
        for (int i = 1; i < 1000_0000; i = i * 2) {
            // 塞入需要计算的值
            histogram.recordValue(i);
        }
        long t1 = System.nanoTime();
        // 求出平均值
        double a = histogram.getMean();
        long t2 = System.nanoTime();
        System.out.println(a + " " + (t2 - t1) + "ns");
    }

    // A Histogram covering the range from 1 nsec to 1 hour with 3 decimal point resolution:
    static Histogram histogram = new Histogram(3600000000000L, 3);

    static public volatile DatagramSocket socket;

    static long WARMUP_TIME_MSEC = 5000;
    static long RUN_TIME_MSEC = 20000;


    static void recordTimeToCreateAndCloseDatagramSocket() {
        long startTime = System.nanoTime();
        try {
            socket = new DatagramSocket();
        } catch (SocketException ex) {
        } finally {
            socket.close();
        }
        long endTime = System.nanoTime();
        histogram.recordValue(endTime - startTime);
    }

    public static void main(final String[] args) {
        long startTime = System.currentTimeMillis();
        long now;

        do {
            recordTimeToCreateAndCloseDatagramSocket();
            now = System.currentTimeMillis();
        } while (now - startTime < WARMUP_TIME_MSEC);

        histogram.reset();

        do {
            recordTimeToCreateAndCloseDatagramSocket();
            now = System.currentTimeMillis();
        } while (now - startTime < RUN_TIME_MSEC);

        System.out.println("Recorded latencies [in usec] for Create+Close of a DatagramSocket:");

        histogram.outputPercentileDistribution(System.out, 1000.0);

    }
}
